import java.util.Stack;

public class Practice1 {
    /*
    链接https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=295&tqId=726&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page@
    用栈来实现这个括号匹配, 也可以利用StringBuilder来手动实现一个栈
     */
    public boolean isValid (String s) {
        // write code here
        char[] ss = s.toCharArray();
        int n = ss.length;
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < n;i++){
            //左括号先入栈
            if(ss[i] == '[' || ss[i] == '('|| ss[i] == '{'){
                stack.push(ss[i]);
            }else{
                //右括号先判断栈中是否有能匹配的左括号
                if(!stack.isEmpty()){
                    //直接弹出来对比
                    char cur = stack.pop();
                    //枚举, 不满足退出, 满足则继续
                    if(ss[i] == ']' && cur != '['){
                        return false;
                    }else if(ss[i] == ')' && cur != '('){
                        return false;
                    }else if(ss[i] == '}' && cur != '{'){
                        return false;
                    }
                }else{
                    return false;
                }

            }
        }
        return stack.isEmpty();
    }
}
